/** An implementation of the Merge Sort divide and conquer sorting algorithm. */
public class MergeSort
{
    private static int count = 0;

    /**
     * Uses the merge sort algorithm to sort the array of integers in {@code
     * &theta(lgn)} time.
     *
     * @param list a list of {@code ints} in arbitrary order
     * @return the original list in sorted, ascending order.
     */
    public static int[] sortInts(int[] list)
    {
        mergeSort(list, 0, list.length - 1);
        System.out.println(count);
        return list;
    }

    //uses depth first divide and conquer to create smaller and smaller sub-arrays
    private static void mergeSort(int[] list, int first, int last)
    {
        count++;

        if (first < last) {
            int middle = first + (last - first) / 2;

            mergeSort(list, first, middle);
            mergeSort(list, middle + 1, last);
            merge(list, first, middle, last);
        }
    }

    private static void merge(int[] list, int first, int middle, int last)
    {
        if (list.length <= 1)
            return;

        int[] left = new int[middle - first + 1];
        int[] right = new int[last - middle];
        boolean leftEmpty = false, rightEmpty = false;

        //copy to left and right subarrays
        System.arraycopy(list, first, left, 0, middle - first + 1);
        System.arraycopy(list, middle + 1, right, 0, last - middle);

        int j = 0, k = 0;
        for (int i = first; i <= last; i++) {

            if (leftEmpty) {
                list[i] = right[k];
                k++;
                continue;
            }
            else if (rightEmpty) {
                list[i] = left[j];
                j++;
                continue;
            }

            if (j < left.length && k < right.length && (left[j] < right[k])) {
                list[i] = left[j];
                j++;

                if (j >= left.length)
                    leftEmpty = true;
            }
            else {
                list[i] = right[k];
                k++;

                if (k >= right.length)
                    rightEmpty = true;
            }
        }
    }

}
